package interview.levenshteindistance;

public class LevenshteinDistance {
	public int distance(String source, String target) {
		// initialize base solutions
		int[][] DPTable = new int[source.length() + 1][target.length() + 1];
		for(int i = 0; i <= target.length(); i++) {
			DPTable[0][i] = i;
		}
		for(int i = 0; i <= source.length(); i++) {
			DPTable[i][0] = i;
		}

		// Dynamic programming, bottom up
		for(int i = 1; i <= source.length(); i++) {
			for(int j = 1; j <= target.length(); j++) {
				if(source.charAt(i-1) == target.charAt(j-1)) {
					DPTable[i][j] = DPTable[i-1][j-1];
				} else {
					int min = DPTable[i-1][j] + 1;
					if(DPTable[i-1][j-1] + 1 < min) {
						min = DPTable[i-1][j-1] + 1;
					}
					if(DPTable[i][j-1] + 1< min) {
						min = DPTable[i][j-1] + 1;
					}
					DPTable[i][j] = min;
				}
			}
		}
		
		printDTTable(DPTable);

		return DPTable[source.length()][target.length()];
	}
	
	private void printDTTable(int[][] DPTable) {
		for(int i = 0; i < DPTable.length; i++) {
			for(int j = 0; j < DPTable[i].length; j++) {
				System.out.print("\t" + DPTable[i][j]);
			}
			System.out.println();
		}
	}
}
